Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,

Given 1->4->3->2->5->2 and x = 3,

return 1->2->2->4->3->5.

Solution:

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode(int x) { val = x; }
  7.  * }
  8.  */
  9. public class Solution {
  10.   public ListNode partition(ListNode head, int x) {
  11.     if (head == null) {
  12.       return null;
  13.     }
  15.     // create fake heads
  16.     ListNode f1 = new ListNode(0);
  17.     ListNode f2 = new ListNode(0);
  19.     ListNode p1 = f1;
  20.     ListNode p2 = f2;
  22.     ListNode node = head;
  23.     while (node != null) {
  24.       if (node.val < x) {
  25.         p1.next = node;
  26.         p1 = p1.next;
  27.       } else {
  28.         p2.next = node;
  29.         p2 = p2.next;
  30.       }
  31.       node = node.next;
  32.     }
  34.     p1.next = f2.next;
  35.     p2.next = null;
  37.     return f1.next;
  38.   }
  39. }